// 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
// 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
// 输入："abc"
// 输出：3
// 解释：三个回文子串: "a", "b", "c"
// 思路，暴力解法，两层for循环，遍历区间起始位置和终止位置，还需一层遍历判断这个区间是不是回文，时间复杂度是On^3

// 思路，动态规划
// 1. 确定dp数组，基于回文的特性，我们需要把dp数组定义成二维dp数组，`dp[i][j]`，区间`[i, j]`的子串是否是回文子串
// 2. 确定递推公式
//     1. `s[i] !== s[j]`,`dp[i][j] = false`
//     2. `s[i] === s[j]`
//         1. 当`i===j`,一个字符，是回文子串
//         2. 当i和j相差1，是回文子串
//         3. 当i和j相差大于1，依赖于`[i+1, j-1]`区间是不是回文子串
// ```js
// if(s[i] !== s[j]) {
//     dp[i][j] = false
// } else {
//     if(j - i <= 1) {
//         result++
//         dp[i][j] = true
//     } else if(dp[i+1][j-1]) {
//         result++
//         dp[i][j] = true
//     }
// }
// ```
// 3. dp数组初始化，都初始化为false
// 4. 确定遍历顺序，`dp[i+1][j-1]`在`dp[i][j]`的左下角，所以一定要从下到上，从左到右遍历
// 5. 举例推导
// 时间复杂度：O(n^2)
// 空间复杂度：O(n^2)
function countSubstrings(s) {
    let result = 0
    let dp = new Array(s.length).fill(0).map(_ => new Array(s.length).fill(false))
    for (let i = s.length - 1; i >= 0; i--) {
        for (let j = i; j < s.length; j++) {
            if (s[i] !== s[j]) {
                dp[i][j] = false
            } else {
                if (j - i <= 1) {
                    result++
                    dp[i][j] = true
                } else if (dp[i + 1][j - 1]) {
                    result++
                    dp[i][j] = true
                }
            }
        }        
    }
    return result
}

console.log(countSubstrings("aaa"))

// 思路2，双指针法
// 找中心然后向两边扩散看是不是对称
// 以一个元素为中心点或者以两个元素为中心点
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
function countSubstrings2(s) {
    let result = 0
    function extend(i, j) {
        let res = 0
        while (i >= 0 && j < s.length && s[i] === s[j]) {
            i--
            j++
            res++
        }
        return res
    }
    for (let i = 0; i < s.length; i++) {
        result += extend(i, i)
        result += extend(i, i + 1)
    }
    return result
}

console.log(countSubstrings2("aaa"))